package com.shigen.demo.datastruct.linkedList;

/**
 * 手写双向链表
 *
 * @author shigenfu
 * @date 2022/7/14 10:03 下午
 */
public class MyLinkedList {

  static class ListNode {

    int value;
    ListNode next;

    public ListNode(int value) {
      this.value = value;
    }
  }

  private ListNode head, tail;
  private int size;

  public MyLinkedList() {
    head = tail = null;
    size = 0;
  }

  /**
   * 获得链表下标对应的元素
   */
  public Integer get(int index) {
    if (head == null) {
      return null;
    }
    if (index < 0 || index > size - 1) {
      return null;
    }
    // 在链表中遍历，获得节点对应的值
    ListNode temp = head;
    for (int i = 0; i < index; i++) {
      temp = temp.next;
    }
    return temp.value;
  }

  /**
   * 在链表头中添加元素
   */
  public void addAtHead(int value) {
    if (head == null) {
      head = tail = new ListNode(value);
    } else {
      ListNode newNode = new ListNode(value);
      newNode.next = head;
      head = newNode;
    }
    size++;
  }

  /**
   * 在链表尾中添加元素
   */
  public void addAtTail(int value) {
    if (head == null) {
      head = tail = new ListNode(value);
    } else {
      ListNode newNode = new ListNode(value);
      tail.next = newNode;
      tail = newNode;
    }
    size++;
  }

  /**
   * 在相应的下标添加元素
   */
  public void addAtIndex(int index, int value) {
    if (index > size) {
      return;
    }
    if (head == null) {
      addAtHead(value);
    } else if (index == size) {
      addAtTail(value);
    } else {
      ListNode temp = head;
      for (int i = 0; i < index - 1; i++) {
        temp = temp.next;
      }
      ListNode newNode = new ListNode(value);
      newNode.next = temp.next;
      temp.next = newNode;
      size++;
    }
  }

  /**
   * 在相应的下标删除元素
   */
  public void deleteAtIndex(int index) {
    if (head == null) {
      return;
    }
    if (index > size - 1 || index < 0) {
      return;
    }
    if (index == 0) {
      // 头删除
      head = head.next;
    } else {
      ListNode temp = head;
      for (int i = 0; i < index - 1; i++) {
        temp = temp.next;
      }
      if (index == size - 1) {
        // 尾删除
        temp.next = null;
        tail = temp;
      } else {
        temp.next = temp.next.next;
      }
    }
    size--;
  }

  /**
   * 打印链表中的元素
   */
  public void print() {
    ListNode temp = head;
    for (int i = 0; i < size; i++) {
      System.out.print(temp.value + " ");
      temp = temp.next;
    }
  }

  /**
   * 获得链表的长度
   */
  public int getSize() {
    return size;
  }

}
